/*!
 * tree-helper v1.4.15
 * (c) phphe <phphe@outlook.com> (https://github.com/phphe)
 * Released under the MIT License.
 */

function isArray(v) {
  return Object.prototype.toString.call(v) === '[object Array]'
}

// remove items from array by sorted indexes. indexes example: [0, 2, 6, 8, 9]
// 通过有序的索引集删除数组项. 索引集例子: [0, 2, 6, 8, 9]
function arrayRemove(arr, v) {
  let index
  let count = 0
  while ((index = arr.indexOf(v)) > -1) {
    arr.splice(index, 1)
    count++
  }
  return count
}

function _typeof(obj) {
  let __typeof
  if (typeof Symbol === 'function' && typeof Symbol.iterator === 'symbol') {
    __typeof = function (obj) {
      return typeof obj
    }
  } else {
    __typeof = function (obj) {
      return obj && typeof Symbol === 'function' && obj.constructor === Symbol && obj !== Symbol.prototype ? 'symbol' : typeof obj
    }
  }

  return __typeof(obj)
}

function _toConsumableArray(arr) {
  return _arrayWithoutHoles(arr) || _iterableToArray(arr) || _nonIterableSpread()
}

function _arrayWithoutHoles(arr) {
  if (Array.isArray(arr)) {
    let arr2 = new Array(arr.length)
    let i = 0
    for (; i < arr.length; i++) arr2[i] = arr[i]

    return arr2
  }
}

// 深度优先遍历
// Depth-First-Search
export function depthFirstSearch(obj, handler, childrenKey = 'children', reverse) {
  const rootChildren = isArray(obj) ? obj : [obj] //
  const StopException = function StopException() {}
  const func = function func(children, parent) {
    if (reverse) {
      children = children.slice()
      children.reverse()
    }

    const len = children.length

    for (let i = 0; i < len; i++) {
      const item = children[i]
      const r = handler(item, i, parent)

      if (r === false) {
        // stop
        throw new StopException()
      } else if (r === 'skip children') {
        continue
      } else if (r === 'skip siblings') {
        break
      }

      if (item[childrenKey] != null) {
        func(item[childrenKey], item)
      }
    }
  }

  try {
    func(rootChildren)
  } catch (e) {
    if (e instanceof StopException) {} else {
      throw e
    }
  }
}

// 广度优先遍历
// Breadth-First-Search
export function breadthFirstSearch(obj, handler, childrenKey = 'children', reverse) {
  const rootChildren = isArray(obj) ? obj : [obj] //
  let stack = rootChildren.map((v, i) => {
    return { item: v, index: i }
  })
  if (reverse) {stack.reverse()}
  const _loop = function _loop() {
    const _stack$shift = stack.shift()
    const item = _stack$shift.item
    const index = _stack$shift.index
    const parent = _stack$shift.parent
    const r = handler(item, index, parent)
    if (r === false) {
      // stop
      return {
        v: void 0,
      }
    } else if (r === 'skip children') {
      return 'continue'
    } else if (r === 'skip siblings') {
      stack = stack.filter((v) => {
        return v.parent !== parent
      })
    }
    if (item[childrenKey]) {
      let _stack
      let children = item[childrenKey]
      if (reverse) {
        children = children.slice()
        children.reverse()
      }
      const pushStack = children.map((v, i) => {
        return {
          item: v,
          index: i,
          parent: item,
        }
      })
      (_stack = stack).push.apply(_stack, _toConsumableArray(pushStack))
    }
  }
  while (stack.length) {
    const _ret = _loop()
    switch (_ret) {
      case 'continue':
        continue
      default:
        if (_typeof(_ret) === 'object') return _ret.v
    }
  }
}

function _changeParent(item, parent) {
  const childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children'
  const parentKey = arguments.length > 3 && arguments[3] !== undefined ? arguments[3] : 'parent'
  // remove item from original list
  if (item[parentKey]) {
    arrayRemove(item[parentKey][childrenKey], item)
  }
  item[parentKey] = parent
}

export function getTreeDataFromFlat(data, idKey, parentIdKey) {
  data.forEach((item) => {
    return item.children = data.filter((v) => {
      return v[parentIdKey] === item[idKey]
    })
  })
  return data.filter((item) => {
    return item[parentIdKey] == null
  })
}

export function insertBefore(item, target) {
  const childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children'
  const parentKey = arguments.length > 3 && arguments[3] !== undefined ? arguments[3] : 'parent'
  if (item === target) {return}
  const siblings = target[parentKey][childrenKey]
  let index = siblings.indexOf(target)
  if (siblings[index - 1] !== item) {
    if (item[parentKey] === target[parentKey]) {
      arrayRemove(siblings, item)
      index = siblings.indexOf(target)
    } else {
      _changeParent(item, target[parentKey])
    }
    siblings.splice(index, 0, item)
  }
}

export function insertAfter(item, target) {
  const childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children'
  const parentKey = arguments.length > 3 && arguments[3] !== undefined ? arguments[3] : 'parent'
  if (item === target) {
    return
  }
  const targetParent = target[parentKey]
  const siblings = targetParent[childrenKey]
  let index = siblings.indexOf(target)
  if (siblings[index + 1] !== item) {
    if (item[parentKey] === target[parentKey]) {
      arrayRemove(siblings, item)
      index = siblings.indexOf(target)
    } else {
      _changeParent(item, target[parentKey])
    }
    siblings.splice(index + 1, 0, item)
  }
}

export function prependTo(item, target) {
  const childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children'
  if (item === target) {
    throw 'can\'t prepend to self'
  }
  const targetChildren = target[childrenKey]
  if (targetChildren[0] !== item) {
    _changeParent(item, target)
    targetChildren.splice(0, 0, item)
  }
}

export function appendTo(item, target) {
  const childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children'
  if (item === target) {
    throw 'can\'t append to self'
  }
  const targetChildren = target[childrenKey]
  const targetChildrenLast = targetChildren[targetChildren.length - 1]
  if (targetChildrenLast !== item) {
    _changeParent(item, target)
    targetChildren.push(item)
  }
}
